package 矩阵转换后的秩;

import java.util.ArrayList;
import java.util.TreeMap;

/**
 * @Program:IntelliJ IDEA
 * @description:
 * @author:香蕉你个啵娜娜 l.h-p@qq.com
 * @create:2023-01-25 22:25
 **/

public class Solution {
    public int[][] matrixRankTransform(int[][] matrix) {
        int n = matrix.length, m = matrix[0].length;
        TreeMap<Integer, ArrayList<int[]>> map = new TreeMap<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                map.computeIfAbsent(matrix[i][j], key -> new ArrayList<>()).add(new int[]{i, j});
            }
        }
        int[][] ans = new int[n][m];
        int[] r = new int[n];
        int[] c = new int[m];
        for (int i : map.keySet()) {
            int[] max1 = new int[n], max2 = new int[m];
            for (int[] j : map.get(i)) {
                max1[j[0]] = Math.max(max1[j[0]], r[j[0]]);
                max2[j[1]] = Math.max(max2[j[1]], c[j[1]]);
            }
            for (int[] j : map.get(i)) {
                ans[j[0]][j[1]] = Math.max(max1[j[0]], max2[j[1]]) + 1;
                r[j[0]] = Math.max(r[j[0]], ans[j[0]][j[1]]);
                c[j[1]] = Math.max(c[j[1]], ans[j[0]][j[1]]);
            }
            boolean flag = true;
            while (flag) {
                flag = false;
                for (int[] j : map.get(i)) {
                    if (r[j[0]] != c[j[1]]) flag = true;
                    ans[j[0]][j[1]] = Math.max(r[j[0]], c[j[1]]);
                    r[j[0]] = Math.max(r[j[0]], ans[j[0]][j[1]]);
                    c[j[1]] = Math.max(c[j[1]], ans[j[0]][j[1]]);
                }
            }
        }
        return ans;
    }
}

